public class LeetCode {
    //判断是否为平衡二叉树
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetree(root.left,root.right);
    }
    private boolean isSymmetree(TreeNode p,TreeNode q){
        //判断两棵树结构是否相同
        if(p != null && q == null ||p == null && q != null ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSymmetree(p.left,q.right)&&isSymmetree(p.right,q.left);
    }
    //判断两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || q == null && p != null){
            return false;
        }
        if( p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //二叉树翻转

        public TreeNode invertTree(TreeNode root) {
            if(root == null){
                return null;
            }
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            invertTree(root.left);
            invertTree(root.right);
            return root;
        }

        //判断一棵树是另一颗数的子树
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if(root == null || subRoot == null){
                return false;
            }
            if (isSameTree(root,subRoot)) return true;
            if(isSubtree(root.left,subRoot)) return true;
            if(isSubtree(root.right,subRoot)) return true;
            return false;
        }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || q == null && p != null){
            return false;
        }
        if( p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //二叉树对称
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetree(root.left,root.right);
    }
    private boolean isSymmetree(TreeNode p,TreeNode q){
        //判断两棵树结构是否相同
        if(p != null && q == null ||p == null && q != null ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSymmetree(p.left,q.right)&&isSymmetree(p.right,q.left);
    }
}
